Large distributed computing systems often partition their computational and administrative resources into autonomous units called realms. An entity with its own identity, called a principal, registers its identity with a realm. Examples of principals are a human user of distributed computing systems, a program running on a computer system, a computer system, or a realm itself.
A principal can provide services to other principals, usually through a program running on a computer system. In this case, the principal is called a server and the principals requesting/receiving services are called clients.
Each realm has a server called an authentication server. Suppose two principals, A and B, both register with realm X; and principal A wishes to authenticate (the process of identifying and verifying a principal on the network) itself to principal B. Principal A can do so by requesting realm X's authentication server to generate a certificate. Pertaining to the certificate, a key is also sent to principal A secretly by the authentication server. The knowledge of the key is required to use the certificate correctly. Thus, when principal B is presented with the certificate from principal A, principal B can prove principal A's identity. Realm X's authentication server can generate such a certificate because both principals A and B have registered with realm X, and a realm's authentication server is trusted to certify its registered principals. The Kerberos network authentication protocol, as described within The Kerberos Network Authentication Service (V5), by John Kohl and B. Clifford Neuman, Internet Draft, September 1992, is an example of protocols carrying out such authentication.
A problem arises when principal B is registered with realm Y and not realm X. In this case, neither realm X's nor realm Y's authentication server can generate a certificate for principal A to authenticate itself to principal B. The following references, which are incorporated by reference herein, are all descriptions of prior art attempts to solve this problem: The Kerberos Network Authentication Service (V5), by John Kohl and B. Clifford Neuman, Internet Draft, September 1992; Authentication in Distributed Systems: Theory and Practice, by Butler Lampson, Martin Abadi, Michael Burrows, and Edward Wober, ACM Trans. on Computer Systems, 10(4), November 1992; On Inter-realm Authentication of Large Distributed Systems, by Virgil D. Gligor, Shyh-Wei Luan and Joseph N. Pato, In Proc. of IEEE Computer Society Symposium on Research in Security and Privacy, May 1992; and Hierarchial Trust Relationship for Inter-Cell Authentication, by Joseph N. Pato, OSF/DCE RFC 7.0, Open Software Foundation, July 1992. All these attempted solutions are based on some sort of "co-signature" scheme, which works in the following way:
1. Find a sequence of intermediate realms, R0, R1, . . . , Rn, such that PA1 2. Principal A requests realm X's authentication server to generate certificate C0 to authenticate principal A to realm R1. PA1 3. Principal A requests realm R1's authentication server to generate a new certificate C1 based on certificate C0. Certificate C1, in effect, is a combination of certificate C0 and another certificate which states: realm R1's authentication server certifies that certificate C0 is generated by realm X's authentication server. Certificate C1 is generated in such a way that realm R2's authentication server can verify that certificate C1 is generated by realm R1's authentication server. Certificate C1 can be generated in such a way because realm R1 has registered with realm R2. Certificate C1 can be considered as "certificate C0 co-signed by realm R1's authentication server." PA1 4. By repeating steps similar to 3, principal A requests certificate Ci from realm Ri's authentication server. Each certificate Ci is generated by realm Ri's authentication server, and certifies that certificate C(i-1) is generated by realm R(i-1)'s authentication server. Therefore, each certificate Ci can be considered as "certificate C(i-1) co-signed by realm Ri's authentication server." PA1 5. Principal A eventually acquires certificate Cn and presents certificate Cn to principal B so as to authenticate itself to principal B. Note that certificate Cn is "co-signed" by realms R0, R1, . . . , Rn. PA1 1. A mechanism should be provided for a server to specify its own policy on what kinds of authentication paths are trustworthy to itself and to announce the policy to its clients. A server may choose to reject authentication paths that do not comply with its announced policy. PA1 2. A mechanism should be provided for a client to specify its own policy on what kinds of authentication paths through which it would like to traverse to reach the server's realm. PA1 3. A mechanism should be provided for a client to find an authentication path that complies with both the server's policy and the client's policy (if such a path exists).
(a) Realm X is realm R0, PA2 (b) Realm Y is realm Rn, PA2 (c) Realm Ri registers with realm R(i+1) and realm R(i+1) registers with realm Ri, with i=0, . . . (n-1), PA2 (d) The sequence of realms R0, R1, . . . , Rn, is referred to as an "authentication path".
Three problems need to be addressed in the above co-signature scheme:
None of the prior art solutions cited above provides these policy mechanisms. Furthermore, applications based on these solutions have to devise their own policy mechanism. Additionally, repetitive or incompatible mechanisms may result. Also note that the prior art solutions allow only hierarchical authentication paths to be automatically routed (a hierarchical authentication path is an authentication path that traverses realms within at most two realm hierarchies, where every realm is trusted to authenticate its descendants to its ancestor and to authenticate its ancestor or peers in cross-linked hierarchies to its descendants. A realm hierarchy would usually contain an autonomous unit such as an enterprise, an organization, or a university). Moreover, applications that use authentication paths that involve more than two realm hierarchies would have to devise their own routing mechanisms.
Thus, there is a need in the art for an authentication protocol, which allows a target server to publish (announce) its authentication policy to the network. There is a further need in the art for an authentication protocol that does not impose a particular structure, relationship, or hierarchy on the various realms within the data processing network. There is yet another need in the art for such a protocol that allows a client to specify its own policy on what types of authentication paths it wishes to traverse to a particular server's realm. Additionally, there is a need in the art for an authentication protocol that provides an authentication path to a client, which complies with the authentication policies of the target server and policies specified by the client.